package com.zh.note.leetcode.greedy;

import java.util.Arrays;

/**
 * 1005. K 次取反后最大化的数组和
 * 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
 * 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
 * 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
 * 以这种方式修改数组后，返回数组 可能的最大和 。
 * 输入：nums = [4,2,3], k = 1
 * 输出：5
 * 解释：选择下标 1 ，nums 变为 [4,-2,3] 。
 */
public class LC_1005_largestSumAfterKNegations {
    //
    // public int largestSumAfterKNegations(int[] nums, int k) {
    //     // 按照绝对值的大小降序排列
    //     nums = Arrays.stream(nums).boxed().sorted(new Comparator<Integer>() {
    //         @Override
    //         public int compare(Integer o1, Integer o2) {
    //             return Math.abs(o1) - Math.abs(o2);
    //         }
    //     }).mapToInt(Integer::valueOf).toArray();
    //     for (int i = 0; i < nums.length; i++) {
    //         if (nums[i] < 0 && k > 0) { // 将小于0的元素取反
    //             nums[i] *= -1; //
    //             k--;
    //         }
    //     }
    //     if (k % 2 == 1) { // 如果是k奇数,将最后一个元素取反
    //         nums[nums.length - 1] *= -1;
    //     }
    //     //求和
    //     return Arrays.stream(nums).sum();
    // }
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 按照绝对值的大小降序排列
        nums = Arrays.stream(nums).boxed().sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::valueOf).toArray();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0 && k > 0) { // 将小于0的元素取反
                nums[i] *= -1; //
                k--;
            }
        }
        if (k % 2 == 1) { // 如果是k奇数,将最后一个元素取反
            nums[nums.length - 1] *= -1;
        }
        //求和
        return Arrays.stream(nums).sum();
    }
}
